package leetcode.code;

public class Trie {

	private class Node {
		Node[] c = new Node[26];
		boolean end;
	}

	private Node root;

	public Trie() {
		root = new Node();
	}

	public void insert(String word) {
		Node node = root;
		for (char c : word.toCharArray()) {
			int idx = c - 'a';
			if (node.c[idx] == null)
				node.c[idx] = new Node();
			node = node.c[idx];
		}
		node.end = true;
	}

	public boolean search(String word) {
		Node node = root;
		for (char c : word.toCharArray()) {
			int idx = c - 'a';
			if (node.c[idx] == null)
				return false;
			node = node.c[idx];
		}
		return node.end;
	}

	public boolean startsWith(String prefix) {
		Node node = root;
		for (char c : prefix.toCharArray()) {
			int idx = c - 'a';
			if (node.c[idx] == null)
				return false;
			node = node.c[idx];
		}
		return true;
	}

	public static void main(String[] args) {
		Trie t = new Trie();
		t.insert("hello");
		System.out.println(t.search("hello"));
		System.out.println(t.search("hel"));
		System.out.println(t.search("hellx"));
		System.out.println(t.startsWith("he"));
		System.out.println(t.startsWith("xe"));

	}

}
